//
// Created by 86131 on 2023/10/24.
//
#include <unordered_map>
#include <iostream>
#include <string>
using namespace std;
#include "queue.h"
#ifndef SHUJUJIEGUO_BINARYTREE_H
#define SHUJUJIEGUO_BINARYTREE_H

#endif //SHUJUJIEGUO_BINARYTREE_H
#include "BinaryTreeNode.h"
class BinaryTree{
protected:
    TreeNode* root;
public:
    BinaryTree() : root(nullptr) {}

    virtual void insert(int value) {
        if(root== nullptr){//如果树不存在，那么建立树的第一个结点
            root = new TreeNode(value);
            return;
        }
        queue<TreeNode*> queue;
        queue.push(root);
        //用队列取实现完全二叉树的插入，作为普通的二叉树，那么将采用完全二叉树的插入方式，将元素插入
        while(!queue.empty()){
            TreeNode* curr =queue.front();
            queue.pop();
            if(curr->left== nullptr){//如果其没有左节点，那么直接创建一个左子根
                curr->left = new TreeNode(value);//将值插入
                return;
            }else {
                queue.push(curr->left);//否则就将左结点入队列，方便下一层第一个出队列这个结点
            }
            if(curr->right== nullptr){
                curr->right = new TreeNode(value);
                return;//否则如果右结点没有的话，那么就创建一个右子根
            }else{
                queue.push(curr->right);
            }
        }
    }

    virtual bool search(int value) {
        return searchRecursive(root, value);
    }
    void printInorder() {//中序遍历//LTR
        /*  如果一棵树的元素是ABCDEHGHIJKLMNO的顺序组成了一颗完全二叉树的话
         * 前序遍历:ABDHIEJKCFLMGND
         * 中序遍历:HDIBJEKALMFCNGO
         * 后序遍历:HIDJKEBCMFNOGCA
         * 叶子节点为:HIJKLMNO
         * 我们可以看出来，不管是用什么顺序去遍历的话，叶子节点的顺序是不会发生改变的
         *
         * */
        cout << "Inorder Traversal: ";
        inorderTraversal(root);
        std::cout << std::endl;
    }

    virtual void printPreorder() {//前序遍历//TLR
        std::cout << "Preorder Traversal: ";
        preorderTraversal(root);

        std::cout << std::endl;
    }
    void printPostorder() {//后序遍历//LRT
        std::cout << "Postorder Traversal: ";
        postorderTraversal(root);
        std::cout << std::endl;
    }
    int getHeight(){
        return GetHeight(root);
    }
    int getHeight(TreeNode *node){
        return GetHeight(node);
    }
    TreeNode* printPostorder_and_printInorder_build_tree(string& preorder, string& inorder){
        int n = preorder.length();

        unordered_map<char, int> inorderMap;
        for (int i = 0; i < n; ++i) {
            inorderMap[inorder[i]] = i;  // 将中序遍历序列中每个字符与其索引建立映射关系
        }

        return printPostorder_and_printInorder_buildTreeHelper(preorder, inorder, 0, n - 1, 0, n - 1, inorderMap);
    }
    TreeNode* printPreorder_and_printInorder_build_tree(string& preorder, string& inorder){
        int n = preorder.length();

        unordered_map<char, int> inorderMap;
        for (int i = 0; i < n; ++i) {
            inorderMap[inorder[i]] = i;  // 将中序遍历序列中每个字符与其索引建立映射关系
        }

        return printPostorder_and_printInorder_buildTreeHelper(preorder, inorder, 0, n - 1, 0, n - 1, inorderMap);
    }
private:
    static bool searchRecursive(TreeNode* node,int value) {
        queue<TreeNode*> queue;
        queue.push(node);//查找用没有这个元素，由于我们插入的时候，使用完全二叉树插入的，所以我们查找的时候就只能全部遍历一下了
        while (queue.empty()){
            queue.pop();
            if(node->val ==value){
                return true;
            }
            if(node->left->val==value){
                return true;
            }else{
                queue.push(node->left);
            }
            if(node->right->val==value){
                return true;
            }else{
                queue.push(node->right);
            }
        }
        return false;//如果什么都没有找到的话，那么就会取返回一个false
    }
    void preorderTraversal(TreeNode* node){
        if(node != nullptr) {
            cout << node->val << " ";
            preorderTraversal(node->left);
            preorderTraversal(node->right);
        }
    }
    void inorderTraversal(TreeNode *node){
        if(node!= nullptr){
            inorderTraversal(node->left);
            cout << node->val << " ";
            inorderTraversal(node->right);
        }
    }
    void postorderTraversal(TreeNode* node){
        if(node != nullptr){
            postorderTraversal(node->left);
            postorderTraversal(node->right);
            cout << node->val << " ";
        }
    }
    int GetHeight(TreeNode *node){
        if(node== nullptr){
            return 0;//空的话，高度为0
        }
        int leftHeight = GetHeight(node->left);//递归计算左子树的高度
        int rightHeight = GetHeight(node->right);//递归计算右子树高度
        return max(leftHeight,rightHeight)+1;//返回左右子树高度的较大值加上当前节点的高度+1
    }
    TreeNode* printPostorder_and_printInorder_buildTreeHelper(string& preorder, string& inorder, int preStart, int preEnd, int inStart, int inEnd, unordered_map<char, int>& inorderMap) {
        if (preStart > preEnd || inStart > inEnd) {
            return nullptr;
        }
        // 根据先序遍历的第一个字符创建根节点
        char rootVal = preorder[preStart];
        //如果树不存在，那么建立树的第一个结点
        if(root== nullptr){//如果树不存在，那么建立树的第一个结点
            root = new TreeNode(rootVal);
            int rootIndex = inorderMap[rootVal];

            // 计算左子树的大小和右子树的大小
            int leftSize = rootIndex - inStart;
            int rightSize = inEnd - rootIndex;
            // 递归构建左子树和右子树
            root->left = printPostorder_and_printInorder_buildTreeHelper(preorder, inorder, preStart + 1, preStart + leftSize, inStart, rootIndex - 1, inorderMap);
            root->right = printPostorder_and_printInorder_buildTreeHelper(preorder, inorder, preEnd - rightSize + 1, preEnd, rootIndex + 1, inEnd, inorderMap);

            return root;
        }else{
            TreeNode* root1 = new TreeNode(rootVal);
            int rootIndex = inorderMap[rootVal];

            // 计算左子树的大小和右子树的大小
            int leftSize = rootIndex - inStart;
            int rightSize = inEnd - rootIndex;

            // 递归构建左子树和右子树
            root1->left = printPostorder_and_printInorder_buildTreeHelper(preorder, inorder, preStart + 1, preStart + leftSize, inStart, rootIndex - 1, inorderMap);
            root1->right = printPostorder_and_printInorder_buildTreeHelper(preorder, inorder, preEnd - rightSize + 1, preEnd, rootIndex + 1, inEnd, inorderMap);

            return root1;
        }
    }

};